#include "common.h"

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* searchRange(int* nums, int numsSize, int target, int* returnSize);

int* not_founded(int* returnSize);

int main()
{
	return 0;
}

int* searchRange(int* nums, int numsSize, int target, int* returnSize)
{
	*returnSize = 2;
	int* res = malloc(2 * sizeof(int));
	res[0] = -1, res[1] = -1;

	if (numsSize == 0)
		return res;

	int left = 0, right = numsSize, mid = 0;
	if (nums[numsSize - 1] > target) {
		while (left < right) {
			mid = left + (right - left >> 1);
			if (nums[mid] == target && nums[mid + 1] > target)
				break;
			else if (nums[mid] > target)
				right = mid;
			else
				left = mid + 1;
		}

		if (nums[mid] != target) {
			return res;
		}

		res[1] = mid;
	} else if (nums[numsSize - 1] == target)
		res[1] = numsSize - 1;
	else
		return res;

	left = 0, right = res[1], mid = 0;
	if (nums[0] != target) {
		while (left <= right) {
			mid = left + (right - left >> 1);
			if (nums[mid] == target && nums[mid - 1] < target)
				break;
			else if (nums[mid] < target)
				left = mid + 1;
			else
				right = mid;
		}

		res[0] = mid;
	} else
		res[0] = 0;

	return res;
}
